Chào mừng bạn đến với Bài 3 của Các Khái niệm Trí tuệ Nhân tạo (PolyU COMP5511). Trong buổi học này, chúng ta chuyển từ tìm đường cho một tác nhân sang Tìm kiếm Đối kháng, nơi các tác nhân hoạt động trong môi trường đa tác nhân mang tính cạnh tranh. Chúng ta cũng giới thiệu Bài toán Thỏa mãn Ràng buộc (CSPs), một mô hình mà mục tiêu là tìm ra một trạng thái thỏa mãn một tập hợp ràng buộc cụ thể thay vì tìm một đường đi.
Các Khái niệm Cốt lõi
- Tìm kiếm Đối kháng: Tập trung vào các thuật toán như Minimax và Cắt tỉa Alpha-Beta để đưa ra quyết định hợp lý chống lại một đối thủ thông minh.
- Tìm kiếm Cây Monte Carlo (MCTS): Khám phá việc ra quyết định theo xác suất, đóng vai trò nền tảng cho các AI chơi game hiện đại như AlphaGo.
- Thỏa mãn Ràng buộc: Mô hình hóa bài toán bằng Biến, Miền giá trị và Ràng buộc, được giải quyết bằng Quay lui và Tìm kiếm Cục bộ.
Phân tích Độ phức tạp
Trong môi trường đối kháng, độ phức tạp của không gian tìm kiếm thường được xác định bởi hệ số phân nhánh của trò chơi
Cảnh báo về Sự chuyển đổi Mô hình
Khác với tìm kiếm tiêu chuẩn (ví dụ: A* hoặc BFS) nơi môi trường là tĩnh, Tìm kiếm Đối kháng giả định rằng môi trường (đối thủ) chủ động tìm cách giảm thiểu thành công của bạn. Trong CSPs, thứ tự hành động ít quan trọng hơn tính hợp lệ của kết quả gán cuối cùng.
Mã giả Khái niệm: Các Loại Tác nhân
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).